﻿using System;
using System.Collections.Generic;
using System.Text;

namespace KorTrans
{
    public class Quadtree<T>
    {
        public enum Direction
        {
            NE, SE, SW, NW
        }
        static Quadtree<T> qSentinel = new Quadtree<T>(default(T));
        Quadtree<T> qNE = qSentinel;
        Quadtree<T> qSE = qSentinel;
        Quadtree<T> qSW = qSentinel;
        Quadtree<T> qNW = qSentinel;
        T data;

        public Quadtree(T data)
        {
            this.data = data;
        }

        private Quadtree<T> getSubQuadtree(Direction direction)
        {
            switch (direction)
            {
                case Quadtree<T>.Direction.NE: return qNE;
                case Quadtree<T>.Direction.SE: return qSE;
                case Quadtree<T>.Direction.NW: return qNW;
                case Quadtree<T>.Direction.SW: return qSW;
            }
            return qSentinel;
        }

        public Quadtree<T> GetSubQuadtree(Direction direction)
        {
            if (IsLeaf())
                throw new System.InvalidOperationException("Sub quadtree of a leaf node does not exist.");

            return getSubQuadtree(direction);
        }

        public bool IsLeaf()
        {
            if (qNE == qSentinel && qSE == qSentinel && qSW == qSentinel && qNW == qSentinel)
                return true;
            return false;
        }

        public void SetSubQuadtree(Direction direction, T data)
        {
            switch (direction)
            {
                case Quadtree<T>.Direction.NE: qNE = new Quadtree<T>(data); break;
                case Quadtree<T>.Direction.SE: qSE = new Quadtree<T>(data); break;
                case Quadtree<T>.Direction.NW: qNW = new Quadtree<T>(data); break;
                case Quadtree<T>.Direction.SW: qSW = new Quadtree<T>(data); break;
            }
        }

        public void SetSubQuadtree(Direction direction, Quadtree<T> qtree)
        {
            switch (direction)
            {
                case Quadtree<T>.Direction.NE: qNE = qtree; break;
                case Quadtree<T>.Direction.SE: qSE = qtree; break;
                case Quadtree<T>.Direction.NW: qNW = qtree; break;
                case Quadtree<T>.Direction.SW: qSW = qtree; break;
            }
        }

        private int depth()
        {
            if (this == qSentinel) return 0;

            int ret = 0;
            if (!IsLeaf())
            {
                ret++;
                ret += max(qNW.depth(), qNE.depth(), qSW.depth(), qSE.depth());
            }
            return ret;
        }

        private int max(params int[] x)
        {
            int ret = -1;
            foreach (int i in x)
            {
                if (i > ret)
                    ret = i;
            }
            return ret;
        }

        public override string ToString()
        {
            string ret = toString(this, 0);
            return ret;
        }

        private string toString(Quadtree<T> qtree, int d)        
        {
            if (qtree == qSentinel)
                return "";

            StringBuilder ret = new StringBuilder();
            
            ret.AppendLine(qtree.data.ToString());

            if (!qtree.IsLeaf())
            {
                Quadtree<T> qt = qtree.getSubQuadtree(Quadtree<T>.Direction.NE);
                if (qt != qSentinel) { ret.Append('\t', d); ret.AppendFormat("NE {0}", toString(qt, d + 1)); }
                qt = qtree.getSubQuadtree(Quadtree<T>.Direction.SE);
                if (qt != qSentinel) { ret.Append('\t', d); ret.AppendFormat("SE {0}", toString(qt, d + 1)); }
                qt = qtree.getSubQuadtree(Quadtree<T>.Direction.SW);
                if (qt != qSentinel) { ret.Append('\t', d); ret.AppendFormat("SW {0}", toString(qt, d + 1)); }
                qt = qtree.getSubQuadtree(Quadtree<T>.Direction.NW);
                if (qt != qSentinel) { ret.Append('\t', d); ret.AppendFormat("NW {0}", toString(qt, d + 1)); }
            }

            return ret.ToString();
        }

    }
}
